package com.lsa.letcode.the17.letterComb;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.lang.ArrayUtils;

public class Solution {
	final static Map<Character, char[]> char2Letters = new HashMap<Character, char[]>();
	static {
		char2Letters.put('0', " ".toCharArray());
		char2Letters.put('2', "abc".toCharArray());
		char2Letters.put('3', "def".toCharArray());
		char2Letters.put('4', "ghi".toCharArray());
		char2Letters.put('5', "jkl".toCharArray());
		char2Letters.put('6', "mno".toCharArray());
		char2Letters.put('7', "pqrs".toCharArray());
		char2Letters.put('8', "tuv".toCharArray());
		char2Letters.put('9', "wxyz".toCharArray());
	}
    
    public List<String> letterCombinations(String digits) {
    	List<String> result = new ArrayList<String>();
    	if (!digits.isEmpty()) {
    		char[] solution = new char[digits.length()];
    		iterative(result, digits, 0, solution);
    	}
        return result;
    }
    
    private void iterative(List<String> result, String digits, int pos, char[] solution) {
    	int[] indeces = new int[solution.length];
    	int[] bounds = new int[solution.length];
    	Arrays.fill(indeces, 0);
    	for (int i = 0; i < solution.length; i++) {
			char c = digits.charAt(i);
			char[] letters = char2Letters.get(c);
			bounds[i] = letters.length - 1;
			solution[i] = letters[0];
		}
    	indeces[indeces.length - 1] = -1;
//    	getSolution(digits, indeces, solution);
//		result.add(new String(solution));
    	while(true) {
    		boolean isChanged = false;
    		
    		for (int i = indeces.length - 1; i > -1; --i) {
				if (indeces[i] < bounds[i]) {
					indeces[i]++;
					for (int j = indeces.length - 1; j > i; j--) {
						indeces[j] = 0;
						solution[j] = letter(digits.charAt(j), 0);
					}
					solution[i] = letter(digits.charAt(i), indeces[i]);
//					System.out.println(String.format("%s", Arrays.asList(ArrayUtils.toObject(indeces))));
//					getSolution(digits, indeces, solution);
					result.add(new String(solution));
					isChanged = true;
					break;
				}
			}
    		
    		if (!isChanged) {
    			break;
    		}
    	}
    }
    
//    private void getSolution(String digits, int[] indeces, char[] solution) {
//		for (int i = 0; i < solution.length; i++) {
//    		char c = digits.charAt(i);
//			char[] letters = char2Letters.get(c);
//			solution[i] = letters[indeces[i]];
//    	}
//	}
    
    private static char letter(char digit, int idx) {
		char[] letters = char2Letters.get(digit);
		return letters[idx];
    }
    
    /**
     * Simple recursive solution
     */
    @SuppressWarnings("unused")
	private void yieldCombinations(List<String> result, String digits, int pos, char[] solution)  {
    	if (pos == solution.length) {
    		result.add(new String(solution));
    	}
    	else {
    		char c = digits.charAt(pos);
			char[] letters = char2Letters.get(c);
			for (int j = 0; j < letters.length; j++) {
				solution[pos] = letters[j]; 
				yieldCombinations(result, digits, pos + 1, solution);
			}
    	}
    }
}